package Day2025_04_27;

/**
 * 题目: 选课方案设计
 * 大学里实行学分制。每门课都有一定的学分。每个学生均需要修满规定数量的课程才能毕业。其中有些课程可以直接修读，有些课程需要一定的基础知识，
 * 必须在选了其他一些课程的基础上才能修读。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。假定每门课的直接先修课至多只有一门，
 * 两门课可能存在相同的先修课。例如上表。学生不可能学完大学里开设的所有课程，因此每个学生必须在入学时选定自己要学的课程。每个学生可选课程的总
 * 数目是给定的。现在请你们小组编写一个“学生选课系统”，任意给定一种课程体系（总课程数，课程之间的修读先后制约关系，学生毕业要求修的课程数目），
 * 该系统能帮助学生找出一种选课方案，使得他能得到的学分最多，并且必须满足先修课程优先的原则。表中，该课程体系总共有7门课，每个学生必须修满4门课，
 * 每行代表一门课。每行有2个数，第一个数是这门课程的先修课程课号（0表示该课不存在先修课程），第二个数是这门课程的学分（学分是不超过10的整数）。
 * 在此课程体系下，学生选择课号为：2、6、7、3四门课程得到的学分最多，所得到的学分为13。上面的需求描述中，我们是给定某一课程体系情况下，指定学生
 * 毕业所需修读的课程数，求在此约束下的最多学分选课方案。
 * 【解题要求】
 * 至少一个输入实例的N>100
 * 【输入格式】
 * 第1行， 课程数N
 * 后面的N行，表1中的三列
 * 【输出格式】
 * 第1行， 最高学分
 * 第2行， 选修的4门课程
 *
 *
 * 测试用例:
 * 7
 * 1 2 2
 * 2 0 1
 * 3 0 4
 * 4 2 1
 * 5 7 1
 * 6 7 6
 * 7 2 2
 *
 * 
 * 输出:
 * 13
 * 2, 6, 7, 3
 */

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 1. 使用回溯法将所有的可能性全都排列出来(特殊全排列, 因为只能选4门课, 所以只需要排 4层就可以了),
 * 在使用剪枝将不满足条件的可能剪掉, 约束条件就是先修课号, 先修课号为零的可以不用剪
 * 在判断是否要剪枝的时候可以使用 boolean[]类型的数组判断之前是否修了改门课程 (注意深搜出来之后要恢复现场)
 * 递归出口: 当深搜 4层之后就可以返回值了(判断支是否比之前的最大值要大)
 * 不用设计返回值, 直接设置全局变量在最后全都递归结束后返回这个全局变量就可以了
 * 这里面的难点是函数头, 咱要怎样设计呢?
 * 我们可以直接只在函数头里设置一个参数 n(表示当前的层数), 其余的都用全局变量来设置
 * 时间复杂度 O(N^2)  空间复杂度 O(N)
 */

public class Demo29 {

    // 定义全局变量
    static int N;
    static int[][] arr;

    // 记录当前以选过的课程
    static boolean[] tmp;

    // 记录最大的学分
    static int maxScore;

    // 为最大学分打辅助
    static int ret;

    // 记录得到最大路径的路径
    static List<Integer> maxPath;

    // 为最大路径打辅助
    static List<Integer> path;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入一个数 N (N > 100)
        N = sc.nextInt();

        // 创建一个二维数组存储数据信息
        arr = new int[N + 1][3];

        // 初始化全局变量
        tmp = new boolean[N + 1];
        maxScore = 0;
        ret = 0;
        maxPath = new ArrayList<>();
        path = new ArrayList<>();

        /**
         * 存储数据
         * arr[i][0]: 课号
         * arr[i][1]: 先修课号
         * arr[i][2]: 学分
         */
        for (int i = 1; i <= N; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
            arr[i][2] = sc.nextInt();
        }

        //7
        //1 2 2
        //2 0 1
        //3 0 4
        //4 2 1
        //5 7 1
        //6 7 6
        //7 2 2

        // 开始递归
        // 只需要传递归到第几层就可以了
        dfs (0);

        // 打印最大总学分
        System.out.println(maxScore);

        // 打印最大总学分路径
        for (int i = 0; i < maxPath.size(); i++) {
            System.out.print(maxPath.get(i));
            if (i < maxPath.size() - 1) {
                System.out.print(", ");
            }
        }
    }

    // 设置递归函数
    private static void dfs(int n) {

        // 递归出口
        if (n == 4) {

            // 判断下面是否比之前的最大值要大
            if (ret > maxScore) {
                maxScore = ret;
                maxPath = new ArrayList<>(path);
            }
            return;
        }

        // 主要逻辑
        for (int i = 1; i <= N; i++) {

            // 注意当遇到不想要的数据时怎么跳过, 画详细决策树

            int x = arr[i][1];
            // 如果先修课号不为0, 且之前没有修过, 就跳过
            if (x != 0 && !tmp[x]) {
                continue;
            }

            // 如果之前已经修过, 就跳过
            if (tmp[i]) {
                continue;
            }

            // 先修课程号为0, 或者之前没有修过
            path.add(arr[i][0]);
            ret += arr[i][2];
            tmp[i] = true;

            dfs(n + 1);

            // 恢复现场
            path.remove(path.size() - 1);
            ret -= arr[i][2];
            tmp[i] = false;

        }
    }

}

